/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        //这道题我也不知道到底算不算贪心？
        //思路就是第一步最大覆盖范围为l1 如果没到终点 l1内的点都可以第二次起跳 直到终点
        int res = 0;
        int cur = 0;  //代表当前步数最大扩散范围
        int next = 0; //代表下一步最大扩散范围
        for (int i = 0; i < nums.size() - 1; i++)
        {
            next = max(next, nums[i] + i);
            if (i == cur)
            {
                //i下标到达当前步数的最大扩散范围
                cur = next;
                res++;
                if (next >= nums.size() - 1)
                {
                    break;
                }
            }
        }
        return res;
    }
};
// @lc code=end
